package backtracking;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        backtracing(0, 1, s, new String(), result,0);
        return result;
    }

    private void backtracing(int begin, int end, String s, String current, List<String> result,int count) {
        if (begin >= end) {
            return;
        }
        if (end > s.length()) {
            return;
        }
        if(end-begin>3){
            return;
        }

        if(count>3){
            return;
        }

        if (end - begin > 1 && s.charAt(begin) == '0') {
            return;
        }
        Integer now = Integer.valueOf(s.substring(begin, end));

        if (now >= 0 && now <= 255) {
            if (end == s.length()) {
                if(count==3){
                    result.add(current+now);
                }
                return;
            }
            backtracing(begin, end + 1, s, current, result,count);
            backtracing(end, end + 1, s, current+now+".", result,count+1);
        }
    }


}
